The following prior art references are considered by applicants to be the most pertinent to the present invention:
[A] U.S. Pat. No. 4,888,779, granted Dec. 19, 1989, entitled "Matched Spectral Null Trellis Codes For Partial Response Channels."
[B] Commonly assigned U.S. application Ser. No. 07/869,286, filed Apr. 15, 1992, entitled "Time-Varying Modulo N Trellis Codes For Input Restricted Partial Response Channels," now U.S. Pat. No. 5,257,272, granted Oct. 26, 1993.
[C] Commonly assigned U.S. application Ser. No. 07/869,570, filed Apr. 15, 1992, entitled "Time-Varying Detector For Control Of Error Event Length," now U.S. Pat. No. 5,280,489, granted Jan. 18, 1994.
Partial response channels of interest for data storage devices include those with channel polynomials of the form P(D)=(1-D.sup.n) or (1+D.sup.n), where n is a nonnegative integer. Channels with this form have a practical implementation advantage in that they can be de-interleaved into n separate (1-D) channels or n separate (1+D) channels, respectively. In Reference [A], coding and detection are accomplished by n-way interleaving of appropriate codes for the dicode channel, with polynomial (1-D), or n-way interleaving of appropriate codes for the so-called class-I partial-response channel, with polynomial (1+D).
Reference [A] discloses a method for increasing the reliability of partial response storage channels by increasing the minimum distance between coded output sequences using codes designed to match the spectral nulls in a channel partial response polynomial. The Viterbi detectors in Reference [A] have reduced complexity, achieved by tracking only the spectral content of detected sequences.
The "minimum distance" of a particular detector trellis (sometimes referred to in the art as d.sub.free.sup.2) is defined as the minimum sum of the squared differences between sequences of noiseless sample values resulting from two distinct paths that diverge from a common state on the trellis and remerge to a common state. For partial response maximum likelihood (PRML) detection, d.sub.free.sup.2 is 2, but the first-order matched-spectral null codes of Reference [A] increase d.sub.free.sup.2 to 4. In order to realize the benefits of increased free distance in a Viterbi detector with finite path memory, it is required that any pair of sequences consisting of a coded sequence and another detector trellis sequence accumulate the distance within a finite number of samples. If the code contains "quasi-catastrophic" sequences, which are defined as sequences that are represented by more than one distinct path through the detector trellis, the minimum distance will not be accumulated in a finite number of samples, so it is necessary for the code to avoid such sequences. Reference [A] describes a method for eliminating quasi-catastrophic sequences.
Reference [B] describes a Viterbi detector which replicates a conventional trellis pattern for the desired channel N times. The N copies of the channel response trellis are interconnected in such a way that a preselected function associates each state in the trellis with a particular integer value modulo N. The number N is selected according to the channel detection and coding constraints so that diverging erroneous sequences of minimum distance lead to detector states which are distinct from the correct detector state. Only certain values of the preselectcd function tracked modulo N are allowed every m bits in order to increase the minimum distance between output sequences in the partial response channel and eliminate quasi-catastrophic sequences for increasing the reliability of a data storage device. The codes described in Reference [B] do not match the spectral nulls in the polynomial for the channel.
Reference [C] describes a Viterbi detector based upon a time-varying trellis structure for detection of codes with spectral nulls or spectral-density nulls. The trellis is obtained by selective deletion of states and edges from the trellis that tracks spectral content of sequences. The time-varying structure provides for reduced error-event length by eliminating paths corresponding to certain quasi-catastrophic sequences. However, in order to maintain the desired high code rates, it was necessary to significantly increase the codeword block length or the number of trellis states, resulting in larger code and detector complexity.
There is a need for a trellis coding and detection method that can achieve the high code rate, coding gain (increased minimum distance), runlength constraints for timing/gain control, and reduced error-event lengths that are necessary in storage devices, with less encoder and detector complexity than prior methods.
As herein used, the term "trellis structure" connotes a sequence of trellises, each trellis being defined as comprising one or more subtrellises at the boundaries of which a metric permutation is effected.